1. Field of the Invention
The present invention relates to an apparatus for providing mixed radix projection data from residue number systems data, and more particularly relates to a mixed radix conversion apparatus which provides for error detection and correction.
2. Background of the Invention
There has recently been a renewed interest in the application of residue arithmetic to digital signal processing ("DSP"). By computing DSP functions within a residue number system ("RNS"), the following advantages may be realized:
1. high sampling frequencies PA1 2. modular implementation PA1 3. fault tolerance.
Any DSP implementation which employs residue arithmetic requires the translation of its output from an RNS into a weighted number system ("WNS") while preserving the three advantages listed above.
For example, consider a multistage pipelined system with a cycle time of T seconds. Once every T seconds, a new input is accepted into each stage of the system. The input to the first stage is the system input. Once every T seconds, a new output is produced by each stage. The output of the last stage is the system output. The output of a given stage is the input to its succeeding stage. Each stage may itself be comprised of multiple stages.
FIG. 1 depicts a multistage pipelined system which may be used to process a computational workload. This system, as outlined below, utilizes the technique of redundant residue number system arithmetic to achieve the advantages of fast cycle time, modular implementation, and fault tolerance.
The system input is one or more integers represented within some weighted number system (WNS). The first stage 10 derives a residue number system (RNS) representation of the input integers, performs the necessary computations within this RNS, and produces the desired output in RNS form. The output 12 of the first stage is a set of N residue digits, k.sub.1 through k.sub.N, where N is the number of moduli upon which the RNS is defined. k.sub.N is the high-order residue digit, k.sub.1 is the low-order residue digit. The RNS contains at least two redundant, high-order moduli to allow single-error correction to be performed on the output residue digits.
The second stage 14 produces N sets of N-1 mixed-radix digits. Each set is formed by ignoring the contribution of one of the k.sub.i while performing a mixed-radix conversion (MRC) on the remaining N-1 residue digits. The N-1 mixed-radix digits which result from this MRC are referred to as the ith projection. If none of the k.sub.i is in error, then each projection is a different WNS representation of the desired system output. In the presence of an erroneous residue digit k.sub.i, exactly one of the projections will be a correct WNS representation of the desired system output--it will be the projection which was formed by ignoring the contribution of k.sub.i. It is the second stage with which the invention is concerned.
The third stage 18 uses the output 16 of the second stage 14 to determine the correct output, if possible, and to provide any useful error information. The third stage may also convert the system output into a more convenient WNS representation.
Focusing on the specific computations of such a system, consider an RNS based upon the set of N relatively prime integers EQU {m.sub.1, m.sub.2, . . . , m.sub.N }
which are referred to as the moduli of the RNS. The RNS representation of a natural integer k is written as EQU [k.sub.1, k.sub.2, . . . k.sub.N ]
where k.sub.i is termed a residue digit and represents the value k modulo m.sub.i.
MRC is a useful technique for translating from an RNS into a WNS. An integer k may be represented by a series of weighted mixed-radix digits: ##EQU1## where ##EQU2## are the weights (w.sub.1 =1), and where the d.sub.i are the mixed-radix digits.
MRC may be implemented using an array comprised of Read-Only Memory ("ROM") modules and latches. This structure may be pipelined for increased throughput. FIG. 2 illustrates a prior art pipelined MRC structure which computes the mixed-radix digits, d.sub.i, from the residue digits, k.sub.i, for an RNS with N=4. ROMij stores the function EQU r=((p-q)m.sub.j.sup.-1)modulo m.sub.i ( 3)
where m.sub.j.sup.-1 is an integer such that EQU (m.sub.j.sup.-1 .times.m.sub.j)modulo m.sub.i =1.
Each ROM incorporates an input latch so that the structure is able to process a new set of residue digits every cycle. All latches are clocked together.
MRC structures not only provide translation from RNS to WNS, but also provide a self-checking means for performing error detection and correction--preserving the RNS advantages of modularity and fault-tolerance, as well as the advantage of high sampling frequency. As before, using an RNS with N moduli, of which at least 2 are redundant, it is possible to isolate, and correct for, an error in any one of the residue digits. This may be accomplished by using MRC structures to generate N mixed-radix projections from each set of residue digits. The i.sup.th mixed-radix projection is obtained by computing N-1 mixed-radix digits from a set of N-1 residue digits--the i.sup.th residue digit is omitted from the computation. Examination of the highest-order, mixed-radix digit of each projection allows identification of the faulty residue digit.
If a pipelined system is to produce one output every ROM cycle time, and if the system is also to demonstrate concurrent error detection, then all of the required mixed-radix projections must be computed in parallel during each cycle. This can be accomplished by fully replicating an MRC structure N times. The present invention provides a much more economical solution to this problem.